package 归并排序;
import java.util.Arrays;

public class MergeSort {
    public static int[] lastMergeSort(int[] list1, int[] list2) {
        int i = 0, j = 0, k = 0;
        int[] temp = new int[list1.length + list2.length];//临时数组用来存放新的元素
        while (i < list1.length && j < list2.length) {
            if (list1[i] <= list2[j]) {
                temp[k++] = list1[i++];
            } else {
                temp[k++] = list2[j++];
            }
            if (i == list1.length) {
                while (j < list2.length) {
                    temp[k++] = list2[j++];
                }

            }
            if (j == list2.length) {
                for (; i < list1.length; ) {
                    temp[k++] = list1[i++];
                }
            }
        }
        return temp;
    }

    public static int[] mergeSort(int[] theArray) {
        if (theArray.length == 1) {
            return theArray;
        }
        int mid = (int) theArray.length / 2;
        int[] leftArray = mergeSort(Arrays.copyOfRange(theArray, 0, mid));
        int[] rightArray = mergeSort(Arrays.copyOfRange(theArray, mid, theArray.length));
        return lastMergeSort(leftArray, rightArray);
    }


            public static void main(String[] args){
                int[] theArray={10,1,18,30,23,12,7,5,18,17};
                System.out.println("之前的排序为：");
                for(int t=0;t<theArray.length;t++){
                    System.out.print(theArray[t]+"  ");
                }

                int[] larray={1,4,10};
                int[] rarray={2,6,8,11,15,18};
                int[] result_array=lastMergeSort(larray,rarray);
                int[] resultArray=mergeSort(theArray);
                System.out.println("  ");
                System.out.println("归并排序后的数组为：");
                for(int v:resultArray){
                    System.out.print(v+"  ");
                }
            }
}